home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / ui / OGC / allochblk.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-06  |  7.6 KB  |  298 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1989, Tera Computer Company
  5.  **/
  6.  
  7. #define DEBUG
  8. #undef DEBUG
  9. #include <stdio.h>
  10. #include "runtime.h"
  11. /**/
  12. /* allocate/free routines for heap blocks
  13. /* Note that everything called from outside the garbage collector
  14. /* should be prepared to abort at any point as the result of a signal.
  15. /**/
  16.  
  17. /*
  18.  * Free heap blocks are kept on a list sorted by address.
  19.  * The hb_hdr.hbh_sz field of a free heap block contains the length
  20.  * (in bytes) of the entire block.
  21.  * Neighbors are coalesced.
  22.  */
  23.  
  24. struct hblk *savhbp = (struct hblk *)0;  /* heap block preceding next */
  25.                      /* block to be examined by   */
  26.                      /* allochblk.                */
  27.  
  28. /*
  29.  * Return 1 if there is a heap block sufficient for object size sz,
  30.  * 0 otherwise.  Advance savhbp to point to the block prior to the
  31.  * first such block.
  32.  */
  33. int sufficient_hb(sz)
  34. int sz;
  35. {
  36. register struct hblk *hbp;
  37. struct hblk *prevhbp;
  38. int size_needed, size_avail;
  39. int first_time = 1;
  40.  
  41.     size_needed = WORDS_TO_BYTES(sz>0? sz : -sz);
  42.     size_needed = (size_needed+sizeof(struct hblkhdr)+HBLKSIZE-1) & ~HBLKMASK;
  43. #   ifdef DEBUG
  44.     printf("sufficient_hb: sz = %d, size_needed = 0x%X\n", sz, size_needed);
  45. #   endif
  46.     /* search for a big enough block in free list */
  47.     hbp = savhbp;
  48.     for(;;) {
  49.         prevhbp = hbp;
  50.         hbp = ((prevhbp == (struct hblk *)0)
  51.             ? hblkfreelist
  52.             : prevhbp->hb_next);
  53.  
  54.         if( prevhbp == savhbp && !first_time) {
  55.         /* no sufficiently big blocks on free list */
  56.         return(0);
  57.         }
  58.         first_time = 0;
  59.         if( hbp == (struct hblk *)0 ) continue;
  60.         size_avail = hbp->hb_sz;
  61.         if( size_avail >= size_needed ) {
  62.         savhbp = prevhbp;
  63.         return(1);
  64.         }
  65.     }
  66. }
  67.  
  68. /*
  69.  * Allocate (and return pointer to) a heap block
  70.  *   for objects of size |sz|.
  71.  *
  72.  * NOTE: Caller is responsible for adding it to global hblklist
  73.  *       and for building an object freelist in it.
  74.  *
  75.  * The new block is guaranteed to be cleared if sz > 0.
  76.  */
  77. struct hblk *
  78. allochblk(sz)
  79. long sz;
  80. {
  81.     register struct hblk *thishbp;
  82.     register struct hblk *hbp;
  83.     struct hblk *prevhbp;
  84.     long size_needed,            /* number of bytes in requested objects */
  85.          uninit,                 /* => Found uninitialized block         */
  86.          size_avail;
  87.     int first_time = 1;
  88.  
  89.     char *sbrk();            /* data segment size increasing    */
  90.     char *brk();            /* functions            */
  91.  
  92.     size_needed = WORDS_TO_BYTES(sz>0? sz : -sz);
  93.     size_needed = (size_needed+sizeof(struct hblkhdr)+HBLKSIZE-1) & ~HBLKMASK;
  94. #   ifdef DEBUG
  95.     printf("(allochblk) sz = %x, size_needed = 0x%X\n", sz, size_needed);
  96. #   endif
  97.  
  98.     /* search for a big enough block in free list */
  99.     hbp = savhbp;
  100.     for(;;) {
  101.  
  102.         prevhbp = hbp;
  103.         hbp = ((prevhbp == (struct hblk *)0)
  104.                     ? hblkfreelist
  105.             : prevhbp->hb_next);
  106.  
  107.         if( prevhbp == savhbp && !first_time) {
  108.         /* no sufficiently big blocks on free list, */
  109.         /* let thishbp --> a newly-allocated block, */
  110.         /* free it (to merge into existing block    */
  111.         /* list) and start the search again, this   */
  112.         /* time with guaranteed success.            */
  113.                   int size_to_get = size_needed + hincr * HBLKSIZE;
  114.           extern int holdsigs();
  115.           int Omask;
  116.  
  117.           /* Don't want to deal with signals in the middle of this */
  118.               Omask = holdsigs();
  119.  
  120.                     update_hincr;
  121.             thishbp = HBLKPTR(((unsigned)sbrk(0))+HBLKSIZE-1 );
  122.             heaplim = (char *) (((unsigned)thishbp) + size_to_get);
  123.  
  124.             if( (brk(heaplim)) == ((char *)-1) ) {
  125.                         write(2,"Out of Memory!  Giving up ...\n", 30);
  126.             exit(-1);
  127.             }
  128. #                   ifdef PRINTSTATS
  129.             printf("Need to increase heap size by %d\n",
  130.                    size_to_get);
  131.             fflush(stdout);
  132. #                   endif
  133.             heapsize += size_to_get;
  134.             thishbp->hb_sz = 
  135.             BYTES_TO_WORDS(size_to_get - sizeof(struct hblkhdr));
  136.             freehblk(thishbp);
  137.             /* Reenable signals */
  138.               sigsetmask(Omask);
  139.             hbp = savhbp;
  140.             first_time = 1;
  141.         continue;
  142.         }
  143.  
  144.         first_time = 0;
  145.  
  146.         if( hbp == (struct hblk *)0 ) continue;
  147.  
  148.         size_avail = hbp->hb_sz;
  149.         if( size_avail >= size_needed ) {
  150.         /* found a big enough block       */
  151.         /* let thishbp --> the block      */
  152.         /* set prevhbp, hbp to bracket it */
  153.             thishbp = hbp;
  154.             if( size_avail == size_needed ) {
  155.             hbp = hbp->hb_next;
  156.             uninit = thishbp -> hb_uninit;
  157.             } else {
  158.             uninit = thishbp -> hb_uninit;
  159.             thishbp -> hb_uninit = 1; 
  160.                 /* Just in case we get interrupted by a */
  161.                 /* signal                               */
  162.             hbp = (struct hblk *)
  163.                 (((unsigned)thishbp) + size_needed);
  164.             hbp->hb_uninit = uninit;
  165.             hbp->hb_next = thishbp->hb_next;
  166.             hbp->hb_sz = size_avail - size_needed;
  167.             }
  168.         /* remove *thishbp from hblk freelist */
  169.             if( prevhbp == (struct hblk *)0 ) {
  170.             hblkfreelist = hbp;
  171.             } else {
  172.             prevhbp->hb_next = hbp;
  173.             }
  174.         /* save current list search position */
  175.             savhbp = prevhbp;
  176.         break;
  177.         }
  178.     }
  179.  
  180.     /* set size and mask field of *thishbp correctly */
  181.     thishbp->hb_sz = sz;
  182.     thishbp->hb_mask = -1;  /* may be changed by new_hblk */
  183.  
  184.     /* Clear block if necessary */
  185.     if (uninit && sz > 0) {
  186.         register word * p = &(thishbp -> hb_body[0]);
  187.         register word * plim;
  188.  
  189.         plim = (word *)(((char *)thishbp) + size_needed);
  190.         while (p < plim) {
  191.         *p++ = 0;
  192.         }
  193.     }
  194.     /* Clear mark bits */
  195.     {
  196.         register word *p = (word *)(&(thishbp -> hb_marks[0]));
  197.         register word * plim = (word *)(&(thishbp -> hb_marks[MARK_BITS_SZ]));
  198.         while (p < plim) {
  199.         *p++ = 0;
  200.         }
  201.     }
  202.  
  203. #   ifdef DEBUG
  204.     printf("Returning 0x%X\n", thishbp);
  205.     fflush(stdout);
  206. #   endif
  207.     return( thishbp );
  208. }
  209.  
  210. /*
  211.  * Free a heap block.
  212.  *
  213.  * Assume the block is not currently on hblklist.
  214.  *
  215.  * Coalesce the block with its neighbors if possible.
  216.  
  217.  * All mark words (except possibly the first) are assumed to be cleared.
  218.  * The body is assumed to be cleared unless hb_uninit is nonzero.
  219.  */
  220. void
  221. freehblk(p)
  222. register struct hblk *p;
  223. {
  224. register struct hblk *hbp, *prevhbp;
  225. register int size;
  226.  
  227.     /* savhbp may become invalid due to coalescing.  Clear it. */
  228.     savhbp = (struct hblk *)0;
  229.  
  230.     size = p->hb_sz;
  231.     if( size < 0 ) size = -size;
  232.     size = 
  233.     ((WORDS_TO_BYTES(size)+sizeof(struct hblkhdr)+HBLKSIZE-1)
  234.          & (~HBLKMASK));
  235.     p->hb_sz = size;
  236.  
  237.     prevhbp = (struct hblk *) 0;
  238.     hbp = hblkfreelist;
  239.  
  240.     while( (hbp != (struct hblk *)0) && (hbp < p) ) {
  241.     prevhbp = hbp;
  242.     hbp = hbp->hb_next;
  243.     }
  244.  
  245.     if( (((unsigned)p)+size) == ((unsigned)hbp) ) {
  246.     (p -> hb_uninit) |= (hbp -> hb_uninit);
  247.     p->hb_next = hbp->hb_next;
  248.     p->hb_sz += hbp->hb_sz;
  249.     } else {
  250.     p->hb_next = hbp;
  251.     }
  252.     if( prevhbp == (struct hblk *)0 ) {
  253.     hblkfreelist = p;
  254.     } else if( (((unsigned)prevhbp) + prevhbp->hb_hdr.hbh_sz) ==
  255.         ((unsigned)p) ) {
  256.     (prevhbp->hb_uninit) |= (p -> hb_uninit);
  257.     prevhbp->hb_next = p->hb_next;
  258.     prevhbp->hb_sz += p->hb_sz;
  259.     } else {
  260.     prevhbp->hb_next = p;
  261.     }
  262. }
  263.  
  264. /* Add a heap block to hblklist.  */
  265. void add_hblklist(hbp)
  266. struct hblk * hbp;
  267. {
  268.     if (last_hblk >= &hblklist[MAXHBLKS]) {
  269.     fprintf(stderr, "Not configured for enough memory\n");
  270.     exit(1);
  271.     }
  272.     *last_hblk = hbp;
  273.     hbp -> hb_index = last_hblk;
  274.     last_hblk++;
  275. }
  276.  
  277. /* Delete a heap block from hblklist.  */
  278. void del_hblklist(hbp)
  279. struct hblk * hbp;
  280. {
  281.     register struct hblk ** list_entry;
  282.     last_hblk--;
  283.     /* Let **last_hblk use the slot previously occupied by *hbp */
  284.     list_entry = hbp -> hb_index;
  285.     (*last_hblk) -> hb_index = list_entry;
  286.     *list_entry = *last_hblk;
  287. }
  288.  
  289. /* Initialize hblklist */
  290. void init_hblklist()
  291. {
  292. #   ifdef DEBUG
  293.     printf("Here we are in init_hblklist - ");
  294.     printf("last_hblk = %x\n",&(hblklist[0]));
  295. #   endif
  296.     last_hblk = &(hblklist[0]);
  297. }
  298.